package src.java.medium;

public class Solution912 {
    public static void main(String[] args) {

        int[] nums = {5, 2, 3, 1};

        Solution912 solution912 = new Solution912();
        solution912.sortArray(nums);
    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int p = partition(arr, l, r);
            quickSort(arr, l, p - 1);
            quickSort(arr, p + 1, r);
        }
    }
    //    public static int[] partition(int[] arr, int l, int r) {
//        int less = l - 1;
//        int more = r;
//        while (l < more) {
//            if (arr[l] < arr[r]) {
//                swap(arr, ++less, l++);
//            } else if (arr[l] > arr[r]) {
//                swap(arr, --more, l);
//            } else {
//                l++;
//            }
//        }
//        swap(arr, more, r);
//        return new int[] { less + 1, more };
//    }
    public static int partition(int[] arr, int l, int r) {
        int index = r;
        while (l < r) {
            if (arr[l] <= arr[index]) {
                l++;
            } else if (arr[l] > arr[index]) {
                swap(arr, --r, l);
            }
        }
        boolean flag = arr[l] > arr[index];
        if (flag) swap(arr, l - 1, index);
        else swap(arr, l, index);
        return flag ? l - 1 : l;
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length <= 1) return nums;
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
}
